/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-01-14 22:13:17
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-01-15 11:57:49
 * @FilePath: \leetcode\3.无重复字符的最长子串.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=3 lang=cpp
 *
 * [3] 无重复字符的最长子串
 */

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

// @lc code=start
class Solution
{
public:
    unordered_map<char, int> hash_strs;

    int lengthOfLongestSubstring(const string s)
    {
        int head = 0; // 当前无重复子串的起始
        int max_len = 0;
        int i, len = 0;
        for (i = 0; i < s.size(); i++)
        {
            if (hash_strs.find(s[i]) == hash_strs.end())
            {
                hash_strs[s[i]] = i;
            }
            else if (hash_strs[s[i]] >= head)
            {
                len = i - head;
                if (max_len < len)
                    max_len = len;
                head = hash_strs[s[i]] + 1; // 更新子串
                hash_strs[s[i]] = i;
            }
            else
            {
                hash_strs[s[i]] = i;
            }
        }
        len = i - head;

        return (max_len < len) ? len : max_len;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    string s = "abba";
    cout << solution.lengthOfLongestSubstring(s) << endl;
    return 0;
}